import jdk.nashorn.internal.ir.ReturnNode;

import javax.swing.*;

public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    //解法1:迭代法
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode dummyNode = new ListNode(-1);//创建虚拟头节点
        ListNode cur = dummyNode;//标记当前节点
        while (head != null) {//遍历链表
            if (head.val != val) {
                cur.next = head;
                cur = cur.next;
            }
            head = head.next;
        }
        cur.next = null;//将新链表最后一个节点的 next域置为 null
        return dummyNode.next;
    }
    //解法2:递归
    public ListNode removeElements2(ListNode head, int val) {
        if (head == null) return head;
        head.next = removeElements(head.next,val);
        return head.val == val ? head.next : head;
    }
}